package FloodFill;

import java.util.LinkedList;
import java.util.Queue;

public class NumberOfIslands {
    // 辅助向量数组
    int[] dx = {1,-1,0,0};
    int[] dy = {0,0,-1,1};

    // 辅助布尔数组(记录 `1` 的点是否被遍历过)
    boolean[][] visit;

    int m; // 对应 x 坐标
    int n; // 对应 y 坐标

    public int numIslands(char[][] grid) {
        m = grid.length;
        n = grid[0].length;

        visit = new boolean[m][n]; // 辅助布尔数组规模与 grid 一致

        int ret = 0; // 记录岛屿数量

        // 遍历所给数组
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == '1' && visit[i][j] == false) {
                    // `1` 且没有被遍历过, 岛屿数量 ret++
                    ret++;
                    // 找出该岛范围, 并修改对应 visit 坐标为 true, 表示该岛已被发现
                    bfs(grid, i, j);
                }
            }
        }

        return ret;
    }

    public void bfs(char[][] grid, int OOx, int OOy) {
        // 用队列保存该层原点
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{OOx, OOy});
        // 该点已访问
        visit[OOx][OOy] = true;

        while(!queue.isEmpty()) {
            // 取出上一层节点, 准备遍历下一层节点
            int[] point = queue.poll();
            // 分解点的坐标
            int Ox = point[0];
            int Oy = point[1];

            // bfs: 扫描下一层节点, offer符合要求的点
            for(int i = 0; i < 4; i++) {
                int x = Ox + dx[i];
                int y = Oy + dy[i];

                if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' && visit[x][y] == false) {
                    queue.offer(new int[]{x, y});
                    visit[x][y] = true;
                }
            }
        }
    }
}
